import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 85. 最大矩形
 * https://leetcode-cn.com/problems/maximal-rectangle/
 */
public class Solutions_85 {
    public static void main(String[] args) {
        char[][] matrix = {{'1', '0', '1', '0', '0'},
                           {'1', '0', '1', '1', '1'},
                           {'1', '1', '1', '1', '1'},
                           {'1', '0', '0', '1', '0'}};  // output: 6

//        char[][] matrix = {};  // output: 0

//        char[][] matrix = {{'0'}};  // output: 0

//        char[][] matrix = {{'1'}};  // output: 1

//        char[][] matrix = {{'0', '0'}};  // output: 0

        int result = maximalRectangle(matrix);
        System.out.println(result);
    }

    /**
     * 解题思路：将问题转化为 84 题形式，单调栈实现
     * 将 matrix 的每一行，都看作是一层柱状图
     * 依次遍历每一层，并根据每一层的字符值重新计算 heights 数组
     * 计算规则：当前位置上是 1，那么可以叠加高度，若是 0，那么之前的高度无效，设置为 0
     */
    public static int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return 0;
        }
        int row = matrix.length, col = matrix[0].length;
        int res = 0;
        // 方便计算，建立虚拟头尾指针
        // 头尾指针默认为 0，分别对应开始位置与结束位置
        int[] heights = new int[col + 2];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    // 高度叠加
                    heights[j + 1] += 1;
                } else {
                    // 高度重置为 0
                    heights[j + 1] = 0;
                }
            }
            int curRowRect = getMaxRect(heights);
            res = Math.max(res, curRowRect);
        }
        return res;
    }

    public static int getMaxRect(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int startIndex = stack.pop();
                // 柱子高度 = heights[startIndex]
                // 计算的数量 = i - stack.peek() - 1
                // 关键：数量不是 i - startIndex，而是 stack.peek()
                // 即区间 [start.peek() + 1, i - 1] 区间中的柱子高度最低都是 heights[startIndex]
                int rect = heights[startIndex] * (i - stack.peek() - 1);
                max = Math.max(max, rect);
            }
            // 存储索引
            stack.push(i);
        }
        return max;
    }
}
